public class LongSub {
    public static int[] LIS (int[] arr) {
        int max = 1;  //记录最大长度
        int[] lens = new int[arr.length];  //记录i能构成的最大长度
        int[] flags = new int[arr.length];  //记录最长序列
        flags[0] = arr[0];  //初始化最长序列
        lens[0] = 1;
        for(int i = 1;i < arr.length; i++) {
            if(flags[max - 1] < arr[i]) { //当前元素大于最长序列，可以构成，直接放在后面
                flags[max++] = arr[i];
                lens[i] = max;
            }else if(flags[max - 1] > arr[i]){//当前元素小于最长序列，往前查找进行替换
                int index = findFirst(flags,max,arr[i]);  //更新的是最长序列的元素，不是原始数组
                flags[index] = arr[i];
                lens[i] = index + 1;  //index表示的位置，+1后表示的是长度
            }else {
                lens[i] = max;
            }
        }


        int[] res = new int[max];
        for(int i = arr.length-1;i >= 0; i--) {
            if(lens[i] == max) {
                res[--max] = arr[i];
            }
        }

        return res;
    }
    public static int findFirst(int[] arr,int i, int index) { //查找lens前i-1个元素中小于index的最长序列
        int left = 0;
        int right = i - 1;
        while(left<=right) {
            int mid = (left+right)/2;
            if(arr[mid] < index) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
}
